package com.smzh.service;

import java.util.Stack;

import com.smzh.bean.ListNode;
/**
 * 龟兔算法
 * 
 * @author jun
 *
 */
public class RabbitAndTortoiseAlg {
	public boolean isPalindrome(ListNode head) {
		Stack<ListNode> stack = new Stack<ListNode>();
		ListNode fast = head;
		ListNode slow = head;
		boolean isOwn = false;// 判断奇偶数，默认链表长度为偶数
		while (fast != null) {
			stack.push(slow);
			slow = slow.next;
			fast = fast.next;
			if (fast != null) {
				fast = fast.next;
			} else {
				isOwn = true;// 偶数
			}
		}
		if (isOwn)
			stack.pop();
		boolean f = true;
		while (slow != null) {
			ListNode temp = stack.pop();
			System.out.println(temp);
			if (temp.val != slow.val) {
				f = false;
				break;
			}
			slow = slow.next;
		}
		return f;

	}

	public static void main(String[] args) {
		ListNode head = new ListNode(1);
		ListNode s = new ListNode(2);
		ListNode t = new ListNode(1);
		ListNode f = new ListNode(1);
		ListNode l = new ListNode(1);
		head.next = s;
		s.next = t;
		t.next = f;
		f.next=l;
		RabbitAndTortoiseAlg p = new RabbitAndTortoiseAlg();
		System.out.println(p.isPalindrome(head));

	}
}
